1. Field of the Invention
This invention pertains generally to decoding low density parity check (LDPC) codes, and more particularly to controlling message passing within the decoder in response to odd and even iterations of the decoding process.
2. Description of Related Art
Low-Density Parity-Check (LDPC) codes comprise linear block codes defined by a very sparse parity-check matrix H, and are often proposed as the channel coding solutions for modern wireless communication systems, magnetic storage systems and solid-state drive systems. Medium-rate LDPC codes are used in standards, such as DVB-S2, WiMax (IEEE 802.16e), and wireless LAN (IEEE 802.11n). Furthermore, high-rate LDPC codes have been selected as the channel coding scheme for mmWave WPAN (IEEE 802.15.3c). These recent successes of LDPC codes appear primarily in response to their structures which are readily implemented in partially-parallel decoders. These structured codes, called quasi-cyclic LDPC (QC-LDPC), have been adopted in all the standards mentioned above.
QC-LDPC codes are represented as an array of sub-matrices, such as by the following.
            H      QC        =          [                                                  A                              1                ,                1                                                          ⋯                                              A                              1                ,                t                                                                          ⋮                                                                                          ⋮                                                              A                              s                ,                1                                                          ⋯                                              A                              s                ,                t                                                        ]        ,where each sub-matrix Ai,j is a p×p circulant matrix. A circulant matrix is a square matrix in which each row is a one-step cyclic shift of the previous row, and the first row is a one-step cyclic shift of the last row.
QC-LDPC decoders have a significantly higher throughput than the decoders of random sparse matrices. The QC-LDPC structure guarantees that at least p messages can be computed in a parallel fashion at all times if a flooding schedule is used. It should be appreciated that well-designed QC-LDPC codes perform as well as utilizing random sparse matrices.
The original message-passing schedule, called flooding, updates all the variable-nodes simultaneously using the previously generated check-to-variable messages and then updates all the check-nodes simultaneously using the previously generated variable-to-check messages. Sequential message-passing schedules are used to update the nodes sequentially instead of simultaneously. Several studies show that sequential scheduling not only improves the convergence speed in terms of number of iterations but also outperforms traditional flooding scheduling for a large number of iterations. Different types of sequential schedules exist, such as a sequence of check-node updates and a sequence of variable-node updates. Sequential scheduling can also be referred to as Layered Belief Propagation (LBP), which will be utilized herein to refer to all sequential schedules.
Check-node-centric LBP (C-LBP) is a term which indicates a sequence of check-node updates, and variable-node-centric LBP (V-LBP) indicates a sequence of variable-node updates. Simulations and theoretical results show that LBP converges about twice as fast as flooding because the messages are updated using the most recent information available as opposed to updating several messages with the same pre-update information. C-LBP has the same decoding complexity per iteration as flooding, thus providing a convergence speed increase at no cost. However, V-LBP solutions have a higher complexity per iteration than flooding and C-LBP. This higher complexity arises from the check-to-variable message computations.
Furthermore, QC-LDPC codes where the sub-matrices can have at most one “1” per column and one “1” per row facilitate C-LBP and V-LBP decoding in a partially-parallel fashion. This parity-check matrix structure allows partially-parallel processing for each of the p nodes over the bi-partite graph, and each processor uses the most recent information available. Thus, QC-LDPC structures guarantee that C-LBP and V-LBP can perform partially-parallel computations and maintain a sequential schedule.
However, small-to-medium blocklength high-rate QC-LDPC codes generally require more than one diagonal per sub-matrix, while only allowing one row of sub-matrices. In these cases, the single row of sub-matrices is necessary because multiple rows require the sub-matrix size to be too small to provide the necessary throughput. FIG. 1 is a cyclic-shift diagonal diagram showing the structure of the parity-check matrix of a regular high-rate LDPC code. Diagonal lines represent the “1”s of H. For example, the rate-14/15 LDPC code proposed in the IEEE 802.15.3c standard is a regular code with a similar parity check matrix structure to the one shown in FIG. 1. Its blocklength is 1440, and its check-node degree dc is 45. Therefore, conventional C-LBP decoders cannot be implemented in a partially-parallel fashion.
Accordingly, a need exists for a system and method of decoding LDPC codes with reduced overhead while not increasing error rate or convergence iterations. These needs and others are met within the present invention, which overcomes the deficiencies of previously developed LDPC decoding systems and methods.